Problem statement: zenit15ckh

Hviezdni kamzíci

Počet bodov: 35, časový limit: 1000ms

Veľa ludí pozná binárnych kamzíkov – video o skupine kamzíkov, ktorí si odskákali čísla v binárnej sústave. Pre veľký úspech sa rozhodli toto zopakovať, avšak mierne obmenene. Namiesto binárnej sústavy si za svoju inšpiráciu vzali digitálne hodinky. Nápad bol jednoduchý – kamzíci sa zoradia tak, aby pri pohľade zhora bolo vidieť napísané číslo, pričom cifry vyzerajú ako na digitálnych hodinkách. Potom sa preusporiadajú tak, aby ukazovali číslo o jedna väčšie a toto opakujú, až kým ich to neomrzí.

Hneď ale vysvitlo, že na rôzne čísla treba rôzny počet kamzíkov. Avšak žiaden z nich nebol ochotný ani na chvíľku nebyť súčasťou záberu. Preto sa dohodli, že budú ukazovať len čísla, na ktoré treba práve všetkých zúčastnených kamzíkov, aby nikoho nevynechali.

Čo sa ale nestalo, jeden pomladší kamzík sa pomýlil a pokazil tak celé video. V dnešnej modernej dobe sa však videá dajú upravovať, stačí im len pokračovať a ich editovací tím sa postará o zvyšok. Lenže v tom zmätku zabudli, aké číslo ukazovali naposledy. Naštastie si jeden spomenul, koľko čísel už ukázali.

Úloha

Vašou úlohou je teraz zistiť, aké číslo bolo naposledy ukázané, teda zistiť aké je \(n\)–té najmenšie kladné celé číslo (nula nie je kladná), ktoré sa dá ukázať pomocou práve \(k\) kamzíkov.

Hodinky, ktoré kamzíci majú, ukazujú cifry takto

Kedže jedna palička je jeden kamzík, na ukázanie čísla 4247 by bolo treba 16 kamzíkov.

Vstup a Výstup

Na vstupe dostanete dve čísla \(n\) \((1 \leq n \leq 10^k)\) a \(k\) \((2 \leq k \leq 500)\). Na výstup je potrebné napísať jedno číslo – číslo, ktoré bolo naposledy ukázané. Ak také číslo neexistuje, vypíšte “Impossible” (bez úvodzoviek).

Počas riešenia tejto úlohy sa budú objavovať veľké čísla. Zároveň vyrobiť riešenie v pomalších jazykoch, ktoré stíha časový limit, nemusí byť úplne najľahšie, ale určite sa to dá. Za správne riešenie, ktoré používa najväčšie bežné číselné premenné (long long v C++, int64 v Pascale), môžete získať aspoň 24 bodov.

Aby ste si mohli otestovať, ako rýchlo beží vaše riešenie na testovači, vaše riešenie sa bude testovať aj na štvrtom vzorovom vstupe s parametrami \(2 \cdot 10^{116}\) a \(500\).

Príklady

Input:

5 8

Output:

37

Všetky možné čísla, zložené z ôsmich kamzíkov, sú 10, 16, 19, 27, 37, 44, 57, 61, 72, 73, 75, 91, 141, 177, 411, 717, 771, 1111.

Input:

42 47 

Output:

8680888

Input:

3 4

Output:

Impossible